package myself.a003MergeSort;

import myself.a000util.Constants;
import myself.a000util.Logarithm;

/**
 * @author 叶之越
 * Description
 * Date 2021/1/22
 * Time 13:56
 * Mail 739153436@qq.com
 */
public class MergeSortSmallSum {

    public static void main(String[] args) {
        Logarithm.MergeSort.checkSmallSum(MergeSortSmallSum.class, Constants.normalSort);
//        Logarithm.MergeSort.checkSmallSum(MergeSortSmallSum.class, Constants.normalSort,0,2,10,true);
    }

    public int sort(int[] arr, int left, int right) {
        if (left >= right) {
            return 0;
        }
        int mid = left + ((right - left) >> 1);
        return sort(arr, left, mid) +
                sort(arr, mid + 1, right) +
                merge(arr, left, mid, right);
    }

    private int merge(int[] arr, int left, int mid, int right) {

        /*int ans = 0;
        int sumLeft = left;
        int sumRight = mid + 1;
        int sumAddUp = 0;
        // 特殊情况：1,2,3 | 4,5,6 left下边第一次直接达到阈值
        // 正序排序，从右边开始比较，那么必须将右侧的数全部遍历
        while (sumRight <= right) {
            // 高效求和
            while ( sumLeft <= mid&&arr[sumLeft] < arr[sumRight]) {
                sumAddUp += arr[sumLeft];
                sumLeft++;
            }
            ans += sumAddUp;
            sumRight++;
        }*/

        int ans = 0;
        int sumLeft = left;
        int sumRight = mid + 1;
        // 右边或者左边下标任意一个超出阈值就结束
        // 1,3,5 | 2,4,6  左边达到阈值
        // 1,3,7 | 2,4,6  右边达到阈值
        // 题意等价互换，改为元素右边有多少个数比当前数大，进行累加
        while (sumLeft <= mid && sumRight <= right) {
            if (arr[sumLeft] < arr[sumRight]) {
                ans += (right - sumRight + 1) * arr[sumLeft];
                sumLeft++;
            } else {
                sumRight++;
            }
        }

        int[] temp = new int[right - left + 1];
        int tempIndex = 0;
        int lp = left;
        int rp = mid + 1;

        while (lp <= mid && rp <= right) {
            temp[tempIndex++] = arr[lp] <= arr[rp] ? arr[lp++] : arr[rp++];
        }

        while (lp <= mid) {
            temp[tempIndex++] = arr[lp++];
        }

        while (rp <= right) {
            temp[tempIndex++] = arr[rp++];
        }

        for (int i = 0; i < temp.length; i++) {
            arr[left + i] = temp[i];
        }

        return ans;
    }
}
